package com.salim.leetcode.$124;

import com.salim.leetcode.util.TreeNode;

public class BinaryTreeMaximumPathSum {
    private int max = 0;
    public int maxPathSum(TreeNode root) {
        if(root==null){
            return 0;
        }
        max = root.val;
        loop(root);
        return max;
    }

    public int loop(TreeNode root){
        if(root.left==null && root.right==null){
            max = Math.max(max,root.val);
            return root.val;
        }

        int linkSum = root.val;
        int leftSum = root.val;
        int rightSum = root.val;

        if(root.right!=null){
            int right = loop(root.right);
            linkSum += right;
            if(right>0){
                rightSum += right;
            }
        }
        if(root.left!=null){
            int left = loop(root.left);
            linkSum += left;
            if(left>0){
                leftSum += left;
            }
        }
        //currentRootMax计算的是当前节点为root时的最大值 取左或右 加或不加自己 或左+右+自己 五种可能
        //childMax计算的是返回上级时的最大值 取左或右 加或不加自己 四种可能
        int leftRightMax = Math.max(rightSum,leftSum);
        int currentRootMax = Math.max(linkSum,leftRightMax);
        max = Math.max(max,currentRootMax);
        return leftRightMax;
    }
}
